package com.company.linked;

import com.company.ListNode;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * @author jrue
 * @description https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * @date 2019/11/14 15:28
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
 */
public class MergeKLists {

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(-1);
        ListNode tre = head;

        TreeMap<Integer,Integer> map = new TreeMap<>();
        for (int i = 0; i < lists.length; i++) {
            while (lists[i] != null) {
                map.put(lists[i].val, map.getOrDefault(lists[i].val, 0) + 1);
                lists[i] = lists[i].next;
            }
        }

        for (Map.Entry<Integer, Integer> entry
                : map.entrySet()) {
            Integer value = entry.getValue();
            for (int i = 0; i < value; i++) {
                tre.next = new ListNode(entry.getKey());
                tre = tre.next;
            }

        }

        return head.next;
    }

}
